package com.lw.leetcode.linked.b;

import com.lw.leetcode.linked.ListNode;

import java.util.Random;

/**
 * create by idea
 * 382. 链表随机节点
 *
 * @author lmx
 * @version 1.0
 * @date 2021/12/30 20:47
 */
public class Solution {
    ListNode head;
    Random random;

    public Solution(ListNode head) {
        this.head = head;
        this.random = new Random();
    }

    public int getRandom() {
        int reserve = 0;
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            int r = this.random.nextInt(count) + 1;
            if (r == count) {
                reserve = cur.val;
            }
            cur = cur.next;
        }
        return reserve;
    }

}
